<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>链表的实现</title>
</head>
<body>
    <script>
        // 封装链表的构造函数
    function LinkedList (){
            // 封装一个Node类 用于保存每个节点的信息
            function Node(element){
                this.element = element
                this.next = null
            }
    
            // 链表中的属性
            this.length = 0 // 链表的长度
            this.head = null // 链表的第一个节点
    
            /** 链表中的方法 **/
             // 链表尾部追加元素的方法(下面的this都是函数的调用者的this也就是LinkedList)
        LinkedList.prototype.append = function (element){
            // 1.根据新元素创建节点
            var newNode = new Node(element)
    
            // 2.判断原来的链表是否为空
            if(this.head===null){
                this.head = newNode
            } else { // 不为空
                // 2.1.定义变量，保存当前找到的节点
                var current = this.head
                // 循环到最后一个节点
                while(current.next){ // 当这里为null的时候不会进入循环
                    current = current.next
                }
                // 2.2. 找到最后一项 将next赋值为null
                current.next = newNode
            }
            // 3.链表长度加1
            this.length++
        }
    
        // 链表的toString方法用于输出链表的的值
        LinkedList.prototype.toString = function(){
            // 定义两个变量用于存储链表的值以及链表的头
            var current = this.head
            var listString = ''
    
            // 循环遍历链表中所有的元素
            while(current){
                listString += ',' + current.element
                current = current.next
            }
    
            // 返回最终结果 slice(1)的意思是返回所有的值
            return listString.slice(1)
         }

         // 任意位置插入数据
         LinkedList.prototype.insert = function(position, element){
             // 1.检测越界问题:越界插入失败
             if(position<0 || position > this.length) return false
            // 2. 找到正确的位置,并插入数据
            var newNode = new Node(element)
            var current = this.head
            var previous = null
            index = 0 // 用于循环遍历到要插入的位置

            // 3. 判断是否再列表的第一个位置插入
            if(position===0){
                newNode.next= current // 把头部作为插入元素的next了
                this.head = newNode // 把插入的作为头部
            }else{
                // 循环表里要插入的位置
                while(index++<position){
                    previous = current // 把上一个的节点存起来
                    current = current.next // 把下一个节点存起来了
                }
                newNode.next = current  // 当前插入的节点的next是下一个节点
                previous.next = newNode // 上一个节点的next是当前插入的节点
            }
            this.length++
            return true
         }

         // 位置移除数据
         LinkedList.prototype.removeAt = function(position) {
             // 1.判断移除的下标是否超出链表范围
             if(position<0 || position>= this.length) return null
                // 定义变量用于存储信息
                var current = this.head
                var previous = null
                var index = 0
                // 判断是否移除的是第一项
                if(position===0){
                    this.head = current.next // 把第一项的值变成初始时第一项的节点信息
                }else{
                     // 遍历移除的是哪一项
                     while(index++<position){
                         previous = current // 当前节点的上一次的节点信息
                         current = current.next// 当前节点的next
                     }
                     previous.next = current.next // 上一次节点的next变成删除的节点的next（类似取代要删除的节点）
                }
                this.length--
                // 返回移除的数据
                return current.element
         }

         // 获取元素位置
         LinkedList.prototype.indexOf = function (element){
             // 保存头信息
             var current = this.head 
             index = 0
             // 找到元素位置
             while(current){
                 if(current.element === element){
                     return index
                 }
                 index ++
                 current = current.next
             }
             // 来到这里就代表没有找到
             return -1
         }

         // 根据元素删除
         LinkedList.prototype.remove = function (element) {
             var index = this.indexOf(element) /// 查询到元素的下标
             return this.removeAt(index) // 根据下标删除元素
         }

         // 判断链表是否为空
         LinkedList.prototype.isEmpty = function (){
             return this.length === 0
         }

         // 获取链表长度
         LinkedList.prototype.site = function(){
             return this.length
         }

         // 获取第一个元素
         LinkedList.prototype.getFirst = function (){
             return this.head.element
         }


    }    
        // 测试链表
        // 1.创建链表
        var list = new LinkedList()
        // 追加元素
        list.append(15)
        list.append(10)
        list.append(20)
        // 添加到指定位置元素
        list.insert(0,100)
        list.insert(4,200)
        list.insert(2,300)
        alert(list)
        // 测试removeAt方法
        list.removeAt(0)
        list.removeAt(1)
        list.removeAt(3)
        alert(list)
        // 测试indexOf方法
        console.log(list.indexOf(100)); // -1 没找到
        console.log(list.indexOf(20)); // 2 找到了下标为2
        // 测试remove方法
        list.remove(15)
        alert(list)// 10 20
        // 测试其他方法
        alert(list.isEmpty()) // false
        alert(list.site())// 2
        alert(list.getFirst()) // 10
    </script>
</body>
</html>